Koolasuchus được đặt tên năm 1997, hóa thạch lấy từ nhóm Strzelecki tầng Apt trong thành hệ Wonthaggi tại Victoria.[5] Ta biết đến nó nhờ bốn mẫu xương hàm, và nhiều xương sau sọ, gồm xương sườn, đốt sống, một xương mác, và những mảnh đai vai. Một xương hàm tìm thấy năm 1978 ở vùng khai quật tên Punch Bowl gần thị trấn San Remo. Sau đó, những mẫu vật khác được tìm thấy năm 1989 ở Rowell's Beach gần đó. Cái tên Koolasuchus được đặt theo tên nhà cổ sinh vật học Lesley Kool. Tên này còn được đặt nhằm tạo phép chơi chữ với từ "cool" ('mát' trong tiếng Anh), trỏ cái lạnh của môi trường nó sống.[6] Loài điển hình là K. cleelandi, tên loài lấy theo tên nhà địa chất học Mike Cleeland.[1]